题意简述:
给你一个数$n$,求$\phi(n) $的值。
解题思路:
$\phi(n) $即欧拉函数,其一种形式为:
$\phi(n)=n \prod_{i=1}^{n} (\frac{p_n-1}{p_n})$
其中$p$为$n$的质因数,且每个质因数互异,对于符号 $\prod$理解为$ \prod_{i=1}^{n}= A_1 * A_2 * … * A_n $
那这题就变成了简单的分解质因数了,分解完了套公式即可
啥?你不会分解质因数?
那我就赘述一下吧(手动滑稽)
我们知道,任何一个实数$n$,它的质因数均不超过$sqrt(n)$
接着我们从$2$开始枚举($1$不是质数)
当遇到一个能被$n$整除的质数时,我们就得到了$n$的一个质因数$p$
接着,我们让$n$不断整除这个质因数,直到$n\ mod\ p \neq 0$
重复以上步骤,直至$n=1$
POJ也有这道题 (明明是先在POJ做的),听POJ的Dalao说$n=1$时要输出$0$
Tips:建议先乘再除,否则要开long long
代码实现:
1 |
|